{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Advantage Shuffle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #two-pointers #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #双指针 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: advantageCount"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #优势洗牌"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定两个长度相等的数组&nbsp;<code>nums1</code>&nbsp;和&nbsp;<code>nums2</code>，<code>nums1</code>&nbsp;相对于 <code>nums2</code> 的<em>优势</em>可以用满足&nbsp;<code>nums1[i] &gt; nums2[i]</code>&nbsp;的索引 <code>i</code>&nbsp;的数目来描述。</p>\n",
    "\n",
    "<p>返回 <font color=\"#c7254e\" face=\"Menlo, Monaco, Consolas, Courier New, monospace\" size=\"1\"><span style=\"background-color: rgb(249, 242, 244);\">nums1</span></font>&nbsp;的<strong>任意</strong>排列，使其相对于 <code>nums2</code>&nbsp;的优势最大化。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums1 = [2,7,11,15], nums2 = [1,10,4,11]\n",
    "<strong>输出：</strong>[2,11,7,15]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums1 = [12,24,8,32], nums2 = [13,25,32,11]\n",
    "<strong>输出：</strong>[24,32,8,12]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums1.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>nums2.length == nums1.length</code></li>\n",
    "\t<li><code>0 &lt;= nums1[i], nums2[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [advantage-shuffle](https://leetcode.cn/problems/advantage-shuffle/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [advantage-shuffle](https://leetcode.cn/problems/advantage-shuffle/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,7,11,15]\\n[1,10,4,11]', '[12,24,8,32]\\n[13,25,32,11]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        def searchInsert(nums, target):\n",
    "            l,r=0,len(nums)-1\n",
    "            if nums[r]<=target: return l  # 无优势则返回最小\n",
    "            while l<r:\n",
    "                m=l+((r-l)>>1)\n",
    "                if nums[m]<=target: l=m+1\n",
    "                else: r=m\n",
    "            return l\n",
    "        \n",
    "        nums1.sort()\n",
    "        for i,n in enumerate(nums2):\n",
    "            idx=searchInsert(nums1,n)\n",
    "            nums2[i]=nums1[idx]\n",
    "            nums1.pop(idx)\n",
    "        return nums2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        self.nums1=sorted(nums1)\n",
    "        self.nums2=nums2\n",
    "        self.res=[]\n",
    "        for i in nums2:\n",
    "            self.give_out(i)\n",
    "        return self.res\n",
    "\n",
    "    def give_out(self,num_in_nums2):\n",
    "        if num_in_nums2>=self.nums1[-1]:\n",
    "            self.res.append(self.nums1.pop(0))\n",
    "        else:\n",
    "            target=self.search(num_in_nums2)\n",
    "            self.res.append(self.nums1.pop(target))\n",
    "\n",
    "    def search(self,num_in_nums2):\n",
    "        left=0\n",
    "        right=len(self.nums1)-1\n",
    "        while left<right:\n",
    "            mid=left+int((right-left)/2)\n",
    "            if self.nums1[mid]<=num_in_nums2:\n",
    "                left=mid+1\n",
    "            else:right=mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        nums1.sort()\n",
    "        ans = []\n",
    "        def left_bound(target):\n",
    "            left, right = 0, len(nums1) - 1\n",
    "            temp = 0\n",
    "            while left <= right:\n",
    "                mid = (left + right) // 2\n",
    "                if nums1[mid] > target:\n",
    "                    right = mid - 1\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            \n",
    "            if left < len(nums1):\n",
    "                temp = left\n",
    "            else:\n",
    "                temp = 0\n",
    "            ans.append(nums1[temp])\n",
    "            nums1.pop(temp)\n",
    "        for i in range(len(nums2)):\n",
    "            left_bound(nums2[i])\n",
    "        return ans\n",
    "\n",
    "    \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        nums1.sort()\n",
    "        ans = []\n",
    "        for n in nums2:\n",
    "            i = bisect.bisect(nums1, n)\n",
    "            if i == len(nums1):\n",
    "                ans.append(nums1.pop(0))\n",
    "            else:\n",
    "                ans.append(nums1.pop(i))\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        nums1.sort()\n",
    "        for num2 in nums2:\n",
    "            if nums1[-1] <= num2:\n",
    "                res.append(nums1.pop(0))\n",
    "            else:\n",
    "                left = 0\n",
    "                right = len(nums1)\n",
    "                while left <= right:\n",
    "                    mid = (left+right)//2\n",
    "                    if nums1[mid] > num2:\n",
    "                        right = mid -1\n",
    "                    else:\n",
    "                        left = mid + 1\n",
    "                res.append(nums1.pop(right+1))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        nums1.sort()\n",
    "        res = []\n",
    "        for val in nums2:\n",
    "            ix_nums1 = bisect.bisect_right(nums1, val)\n",
    "            if ix_nums1==len(nums1):\n",
    "                # no ans\n",
    "                res.append(nums1.pop(0))\n",
    "            else:\n",
    "                val_nums1 = nums1.pop(ix_nums1)\n",
    "                res.append(val_nums1)\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        nums1.sort()\n",
    "        m = nums1.copy()\n",
    "        flag = [0] * n\n",
    "        def binarySearch(val: int) -> int:\n",
    "            left, right = 0, n - 1\n",
    "            while left <= right:\n",
    "                mid = (left + right) // 2\n",
    "                if m[mid] <= val:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            while left < n and flag[left] == 1: left += 1\n",
    "            if left >= n: left = 0\n",
    "            while left < n and flag[left] == 1: left += 1\n",
    "            return left\n",
    "\n",
    "        for i in range(n):\n",
    "            idx = binarySearch(nums2[i])\n",
    "            nums1[i] = m[idx]\n",
    "            flag[idx] = 1\n",
    "        return nums1\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_right\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        nums1.sort()\n",
    "        ans = []\n",
    "        for n in nums2:\n",
    "            i = bisect_right(nums1, n)\n",
    "            if i < len(nums1):\n",
    "                ans.append(nums1.pop(i))\n",
    "            else:\n",
    "                ans.append(nums1.pop(0))\n",
    "        return ans\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    pass\n",
    "    # print(Solution().advantageCount([2, 0, 4, 1, 2], [1, 3, 0, 0, 2]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        nums1 = sorted(nums1)\n",
    "\n",
    "        def bisearch_right(arr, tar):\n",
    "            l = 0\n",
    "            r = len(arr) - 1\n",
    "            find = -1\n",
    "            while l <= r:\n",
    "\n",
    "                mid = (l+r) // 2\n",
    "                if arr[mid] > tar:\n",
    "                    find = mid\n",
    "                    r = mid - 1\n",
    "                elif arr[mid] <= tar:\n",
    "                    l = mid + 1\n",
    "            return find\n",
    "        \n",
    "        res = [-1] * len(nums1)\n",
    "        for i in range(len(nums2)):\n",
    "            idx = bisearch_right(nums1, nums2[i])\n",
    "            if idx == -1:\n",
    "                pass\n",
    "            else:\n",
    "                res[i] = nums1.pop(idx)\n",
    "        \n",
    "        for i in range(len(res)):\n",
    "            if res[i] == -1:\n",
    "                res[i] = nums1.pop(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        s1=SortedList()\n",
    "        s1.update(nums1)\n",
    "        nums=[]\n",
    "        for num in nums2:\n",
    "            index=s1.bisect_right(num)\n",
    "            if index==len(s1):\n",
    "                nums.append(s1[0])\n",
    "                s1.remove(s1[0])\n",
    "            else :\n",
    "                nums.append(s1[index])\n",
    "                s1.remove(s1[index])\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        nums1 = sorted(nums1)\n",
    "        new_nums1 = [None] * len(nums1)\n",
    "        for idx, num2 in enumerate(nums2):\n",
    "            nums1_idx = 0\n",
    "            l_idx = 0\n",
    "            r_idx = len(nums1)\n",
    "            mid_idx = 0\n",
    "            if num2 < nums1[0]:\n",
    "                nums1_idx = 0\n",
    "            elif num2 < nums1[-1]:\n",
    "                while True:\n",
    "                    mid_idx = (l_idx + r_idx) // 2\n",
    "                    if num2 < nums1[mid_idx] and num2 >= nums1[mid_idx - 1]:\n",
    "                        nums1_idx = mid_idx\n",
    "                        break\n",
    "                    if num2 >= nums1[mid_idx]:\n",
    "                        l_idx = mid_idx\n",
    "                    else:\n",
    "                        r_idx = mid_idx\n",
    "            new_nums1[idx] = nums1[nums1_idx]\n",
    "            nums1.pop(nums1_idx)\n",
    "        return new_nums1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        sorted_nums1 = sorted(nums1)\n",
    "        result = []\n",
    "        for num in nums2:\n",
    "            idx = bisect.bisect_right(sorted_nums1, num)\n",
    "            if idx == len(sorted_nums1):\n",
    "                result.append(sorted_nums1.pop(0))\n",
    "            else:\n",
    "                result.append(sorted_nums1.pop(idx))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        nums1.sort()\n",
    "        ans = [0] * len(nums1)\n",
    "        ids = sorted(range(len(nums2)),key = lambda i:nums2[i])\n",
    "        left = 0\n",
    "        right = len(nums1) - 1\n",
    "        for x in nums1:\n",
    "            if x > nums2[ids[left]]:\n",
    "                ans[ids[left]] = x \n",
    "                left += 1\n",
    "            else:\n",
    "                ans[ids[right]] = x \n",
    "                right -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList as SL\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        sl = SL(nums1)\n",
    "        ans = []\n",
    "        n = len(nums1)\n",
    "        for i in range(n):\n",
    "            p = sl.bisect_left(nums2[i] + 1)\n",
    "            if p < len(sl):\n",
    "                ans.append(sl.pop(p))\n",
    "            else:\n",
    "                ans.append(sl.pop(0))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        sorted_nums1 = sorted(nums1)\n",
    "        idx_2 = [i for i in range(n)]\n",
    "        idx_2.sort(key=lambda x:nums2[x])\n",
    "        left, right = 0, n-1\n",
    "        res = [0 for _ in range(n)]\n",
    "        for i in sorted_nums1:\n",
    "            if i > nums2[idx_2[left]]:\n",
    "                res[idx_2[left]] = i\n",
    "                left += 1\n",
    "            else:\n",
    "                res[idx_2[right]] = i\n",
    "                right -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1, nums2):\n",
    "        n=len(nums1)\n",
    "        nums1=sorted(nums1,reverse=True)\n",
    "        index=sorted([i for i in range(n)],key=lambda i:nums2[i],reverse=True)\n",
    "        i,j=0,n-1\n",
    "        k=0\n",
    "        newnums1=[0 for x in range(n)]\n",
    "        while i<=j:\n",
    "            if nums1[i]<=nums2[index[k]]:\n",
    "                newnums1[index[k]]=nums1[j]\n",
    "                j-=1\n",
    "            elif nums1[i]>nums2[index[k]]:\n",
    "                newnums1[index[k]]=nums1[i]\n",
    "                i+=1\n",
    "            k+=1\n",
    "        return newnums1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        nums1.sort()\n",
    "\n",
    "        idx = list(range(n))\n",
    "        idx.sort(key = lambda x: nums2[x])\n",
    "\n",
    "        l, r = 0, n-1\n",
    "        for i in range(n):\n",
    "            if nums1[i] <= nums2[idx[l]]:\n",
    "                nums2[idx[r]] = nums1[i]\n",
    "                r -= 1\n",
    "            else:\n",
    "                nums2[idx[l]] = nums1[i]\n",
    "                l += 1\n",
    "        return nums2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        n = len(nums2)\n",
    "        arg_ids = sorted(range(n), key=lambda x: nums2[x])\n",
    "        nums3 = sorted(nums1)\n",
    "        ret = [0] * n\n",
    "        l, r = 0, n-1\n",
    "        for num3 in nums3:\n",
    "            if num3 > nums2[arg_ids[l]]:\n",
    "                ret[arg_ids[l]] = num3\n",
    "                l += 1\n",
    "            else:\n",
    "                ret[arg_ids[r]] = num3\n",
    "                r -= 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        nums1.sort()\n",
    "        n = len(nums2)\n",
    "        idx = [i for i in range(n)]\n",
    "        idx.sort(key= lambda x:nums2[x])\n",
    "        res = [0] * n\n",
    "        l = 0\n",
    "        r = n-1\n",
    "        for x in nums1:\n",
    "            if x > nums2[idx[l]]:\n",
    "                res[idx[l]] = x\n",
    "                l+=1\n",
    "            else:\n",
    "                res[idx[r]] = x\n",
    "                r -=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        res = [0]*n\n",
    "        nums1.sort()\n",
    "        n_2 = sorted(range(n), key = lambda x:nums2[x])\n",
    "        left, right = 0, n-1\n",
    "        for x in nums1:\n",
    "            if x > nums2[n_2[left]]:\n",
    "                res[n_2[left]] = x\n",
    "                left += 1\n",
    "            else:\n",
    "                res[n_2[right]] = x\n",
    "                right -= 1\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        ids = sorted(range(n),key = lambda x: nums2[x])\n",
    "        nums1.sort()\n",
    "        ans = [0 for _ in range(n)]\n",
    "        left,right = 0, n-1\n",
    "\n",
    "        for i in range(n):\n",
    "            if nums1[i] > nums2[ids[left]]:\n",
    "                ans[ids[left]] = nums1[i] \n",
    "                left += 1\n",
    "            else:\n",
    "                ans[ids[right]] = nums1[i]\n",
    "                right -= 1\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        ids = sorted(range(n),key = lambda x: nums2[x])\n",
    "        nums1.sort()\n",
    "        ans = [0 for _ in range(n)]\n",
    "        left,right = 0, n-1\n",
    "\n",
    "        for i in range(n):\n",
    "            if nums1[i] > nums2[ids[left]]:\n",
    "                ans[ids[left]] = nums1[i] \n",
    "                left += 1\n",
    "            else:\n",
    "                ans[ids[right]] = nums1[i]\n",
    "                right -= 1\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList as SL\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        id_list = list(range(n))\n",
    "        # 都是从大到小\n",
    "        nums1.sort(reverse=True)\n",
    "        id_list.sort(key=lambda x: nums2[x], reverse=True)\n",
    "        ans = [0] * n\n",
    "        left, right = 0, n - 1\n",
    "        for id2 in id_list:\n",
    "            if nums1[left] > nums2[id2]:\n",
    "                ans[id2] = nums1[left]\n",
    "                left += 1\n",
    "            else:\n",
    "                ans[id2] = nums1[right]\n",
    "                right -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        ans = [0] * n\n",
    "        nums1.sort()\n",
    "        ids = sorted(range(n), key=lambda i: nums2[i])\n",
    "        left, right = 0, n - 1\n",
    "        for x in nums1:\n",
    "            if x > nums2[ids[left]]:\n",
    "                ans[ids[left]] = x  # 用下等马比下等马\n",
    "                left += 1\n",
    "            else:\n",
    "                ans[ids[right]] = x  # 用下等马比上等马\n",
    "                right -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        n=len(nums1)\n",
    "        ans=[0]*n\n",
    "        nums1.sort()\n",
    "        ids=sorted(range(n),key=lambda i:nums2[i])\n",
    "        left,right=0,n-1\n",
    "        for x in nums1:\n",
    "            if x>nums2[ids[left]]:\n",
    "                ans[ids[left]]=x\n",
    "                left+=1\n",
    "            else:\n",
    "                ans[ids[right]]=x\n",
    "                right-=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        nums1.sort()\n",
    "        nums2_idx = sorted(list(range(len(nums2))), key = lambda x: nums2[x])\n",
    "        left, right = 0, len(nums2) - 1\n",
    "        p = 0\n",
    "        res = [0] * len(nums1)\n",
    "        for p in range(len(nums1)):\n",
    "            if nums1[p] > nums2[nums2_idx[left]]:\n",
    "                res[nums2_idx[left]] = nums1[p]\n",
    "                left += 1\n",
    "            else:\n",
    "                res[nums2_idx[right]] = nums1[p]\n",
    "                right -= 1\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Nums2:\n",
    "    def __init__(self, index, val):\n",
    "        self.index = index\n",
    "        self.val = val\n",
    "\n",
    "    def __lt__(self, other):\n",
    "        return self.val > other.val\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        '''\n",
    "        # 方法一：大顶堆排序nums2\n",
    "        res = [0] * len(nums1)\n",
    "        import heapq as heap\n",
    "        i = 0\n",
    "        nums2_sorted = []\n",
    "        for val in nums2:\n",
    "            nums2_sorted.append(Nums2(i, val))\n",
    "            i += 1\n",
    "        heap.heapify(nums2_sorted)\n",
    "        nums1_sorted = sorted(nums1, reverse=True)\n",
    "\n",
    "        left = 0\n",
    "        right = len(nums1) - 1\n",
    "        while(len(nums2_sorted)):\n",
    "            nums2_max = heap.heappop(nums2_sorted)\n",
    "            nums1_max = nums1_sorted[left]\n",
    "            nums1_min = nums1_sorted[right]\n",
    "            if nums1_max > nums2_max.val:\n",
    "                res[nums2_max.index] = nums1_max\n",
    "                left += 1\n",
    "            else:\n",
    "                res[nums2_max.index] = nums1_min\n",
    "                right -= 1\n",
    "        return res\n",
    "        '''\n",
    "        # 方法二：直接排序nums2，记录其index\n",
    "        n = len(nums1)\n",
    "        res = [0] * n\n",
    "        nums1.sort()\n",
    "        nums2_ids = sorted(range(n), key=lambda i: nums2[i])\n",
    "        left, right = 0, n-1\n",
    "        print(nums1)\n",
    "        print(nums2_ids)\n",
    "\n",
    "        for val in nums1:\n",
    "            print(val)\n",
    "            print(nums2[nums2_ids[left]])\n",
    "            print(\"=\" * 10)\n",
    "            if val > nums2[nums2_ids[left]]:\n",
    "                res[nums2_ids[left]] = val\n",
    "                left += 1\n",
    "            else:\n",
    "                res[nums2_ids[right]] = val\n",
    "                right -= 1\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        idx2 = list(range(len(nums2)))\n",
    "        idx1 = sorted(nums1)\n",
    "        idx2 = sorted(idx2, key = lambda x: nums2[x])\n",
    "        ans = [0] * len(nums1) \n",
    "        left, right = 0,len(nums1)-1\n",
    "        for i in range(len(nums1)):\n",
    "            if idx1[i] > nums2[idx2[left]]:\n",
    "                ans[idx2[left]] = idx1[i]\n",
    "                left += 1\n",
    "            else:\n",
    "                ans[idx2[right]] = idx1[i]\n",
    "                right -= 1 \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        sorted_nums2 = sorted(nums2, reverse = True) # large -> small\n",
    "        nums2_idx = sorted(range(n), key = lambda i: nums2[i], reverse = True) # large -> small\n",
    "\n",
    "        sorted_nums1 = sorted(nums1, reverse = True) # large -> small\n",
    "\n",
    "        ans = []\n",
    "        p = 0\n",
    "        q = n-1\n",
    "        for n2 in sorted_nums2:\n",
    "            if sorted_nums1[p] > n2:\n",
    "                ans.append(sorted_nums1[p])\n",
    "                p += 1\n",
    "            else:\n",
    "                ans.append(sorted_nums1[q])\n",
    "                q -= 1\n",
    "\n",
    "        ans_ordered = [0]*n\n",
    "\n",
    "        i = 0\n",
    "        #print(ans)\n",
    "        #print(nums2_idx)\n",
    "        for idx in nums2_idx:\n",
    "            ans_ordered[idx] = ans[i]\n",
    "            i += 1\n",
    "        \n",
    "        return ans_ordered\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        nums1 = sorted(nums1)\n",
    "        trans = sorted(range(len(nums2)), key=lambda x: nums2[x])\n",
    "        trans = sorted(range(len(nums2)), key=lambda x: trans[x])\n",
    "        nums2 = sorted(nums2)\n",
    "\n",
    "        i = 0\n",
    "        j = len(nums2) - 1\n",
    "        res = [0] * len(nums2)\n",
    "        for idx in range(len(nums1)):\n",
    "            if nums1[idx] > nums2[i]:\n",
    "                res[i] = nums1[idx]\n",
    "                i += 1\n",
    "            else:\n",
    "                res[j] = nums1[idx]\n",
    "                j -= 1\n",
    "        # print(nums2)\n",
    "        # print(res)\n",
    "        return [res[x] for x in trans]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        s1=sorted(nums1)\n",
    "        s2=sorted(nums2)\n",
    "        n=len(s1)\n",
    "        pt=n-1\n",
    "        ret=[-1]*n\n",
    "\n",
    "# Get indices of elements in s1 within nums1\n",
    "        indices2=sorted(range(n),key=lambda i:nums2[i]) #\n",
    "        #indices2 = [nums2.index(x) for x in s2]\n",
    "        for i in range(len(s1)-1,-1,-1):\n",
    "            if s1[pt]<=s2[i]:\n",
    "                continue\n",
    "                \n",
    "            \n",
    "            ret[indices2[i]]=s1[pt]\n",
    "            pt-=1\n",
    "        #print(str(indices2))\n",
    "\n",
    "        for i in range(len(ret)):\n",
    "            if ret[i]==-1:\n",
    "                ret[i]=s1[pt]\n",
    "                pt-=1\n",
    "            \n",
    "\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        s1=sorted(nums1)\n",
    "        s2=sorted(nums2)\n",
    "        n=len(s1)\n",
    "        pt=n-1\n",
    "        ret=[-1]*n\n",
    "\n",
    "# Get indices of elements in s1 within nums1\n",
    "        indices2=sorted(range(n),key=lambda i:nums2[i]) #\n",
    "        #indices2 = [nums2.index(x) for x in s2]\n",
    "        for i in range(len(s1)-1,-1,-1):\n",
    "            if s1[pt]<=s2[i]:\n",
    "                continue\n",
    "                \n",
    "            \n",
    "            ret[indices2[i]]=s1[pt]\n",
    "            pt-=1\n",
    "        print(str(indices2))\n",
    "\n",
    "        for i in range(len(ret)):\n",
    "            if ret[i]==-1:\n",
    "                ret[i]=s1[pt]\n",
    "                pt-=1\n",
    "            \n",
    "\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        n = len(nums2)\n",
    "        arr = list(range(n))\n",
    "        arr = sorted(arr,key=lambda x:nums2[x])\n",
    "        ans = [-1]*n\n",
    "        n1 = []\n",
    "        for i in nums1:\n",
    "            heappush(n1,-i)\n",
    "        p = -heappop(n1)\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if nums2[arr[i]]<p:\n",
    "                ans[arr[i]] = p\n",
    "                p = -1\n",
    "                if n1: p = -heappop(n1)\n",
    "        if p!=-1:\n",
    "            heappush(n1,-p)\n",
    "            for i in range(n-1,-1,-1):\n",
    "                if ans[i] == -1 :\n",
    "                    if n1: ans[i] = -heappop(n1)\n",
    "        return ans\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        sorted_idx2 = sorted(range(len(nums2)),key=lambda x:-nums2[x]) # 大到小排序\n",
    "        nums1.sort()\n",
    "        left = 0\n",
    "        right = len(nums1) - 1\n",
    "        res = [0] * len(nums1)\n",
    "        for idx in sorted_idx2:\n",
    "            if nums2[idx] < nums1[right]: # 硬刚\n",
    "                res[idx] = nums1[right]\n",
    "                right -= 1\n",
    "            else:\n",
    "                res[idx] = nums1[left]\n",
    "                left += 1\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        used = set()\n",
    "        n = len(nums1)\n",
    "        nums1.sort()\n",
    "\n",
    "        for num in nums2:\n",
    "            idx = bisect.bisect_right(nums1, num)\n",
    "            # print(idx)\n",
    "            if idx == n:\n",
    "                idx = 0\n",
    "            while idx in used:\n",
    "                idx += 1\n",
    "                if idx == n:\n",
    "                    idx = 0\n",
    "            # print(idx)\n",
    "            res.append(nums1[idx])\n",
    "            used.add(idx)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        i1,i2 = list(range(n)),list(range(n))\n",
    "        i1.sort(key=lambda x: nums1[x])\n",
    "        i2.sort(key=lambda x: nums2[x])\n",
    "\n",
    "        ans = [0]*n\n",
    "        l,r = 0,n-1\n",
    "        for i in range(n):\n",
    "            if nums1[i1[i]]>nums2[i2[l]]:\n",
    "                ans[i2[l]]=nums1[i1[i]]\n",
    "                l+=1\n",
    "            else:\n",
    "                ans[i2[r]]=nums1[i1[i]]\n",
    "                r-=1\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        idx1, idx2 = list(range(n)), list(range(n))\n",
    "        idx1.sort(key=lambda x : nums1[x])\n",
    "        idx2.sort(key=lambda x : nums2[x])\n",
    "        # print(f\"idx1:{idx1}, idx2:{idx2}\")\n",
    "\n",
    "        ans = [0] * n\n",
    "        l, r = 0, n - 1\n",
    "        for i in range(n):\n",
    "            # print(f\"nums1:{nums1[idx1[i]]}, nums2:{nums2[idx2[l]]}, i:{i}, l:{l}\")\n",
    "            if nums1[idx1[i]] > nums2[idx2[l]]:\n",
    "                # 排序后，我对应位置的元素大于你，那么这个元素就应该要和你的元素放在你的原始位置上（拿优势）\n",
    "                ans[idx2[l]] = nums1[idx1[i]]\n",
    "                l += 1\n",
    "            else:\n",
    "                # 排序后，我对应位置的元素小于你，那么这个元素就应该要和你的元素放在你的原始位置上（兑劣势）\n",
    "                ans[idx2[r]] = nums1[idx1[i]]\n",
    "                r -= 1\n",
    "            # print(f\"ans:{ans}\")\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        idx2 = sorted(range(len(nums2)),key=lambda x:-nums2[x])\n",
    "        nums1 = self.sort(nums1)\n",
    "        # nums1.sort()\n",
    "\n",
    "        left,right=0,len(nums1)-1\n",
    "        res = [0]*len(nums1)\n",
    "        for i in idx2:\n",
    "            if nums2[i]>=nums1[right]:\n",
    "                res[i] = nums1[left]\n",
    "                left += 1\n",
    "            else:\n",
    "                res[i] = nums1[right]\n",
    "                right -= 1\n",
    "        return res\n",
    "\n",
    "    def sort(self,arr):\n",
    "        if len(arr)==0:return arr\n",
    "        if len(arr)==1:return arr\n",
    "        idx = random.randint(0,len(arr)-1)\n",
    "        base = arr[idx]\n",
    "        arr.remove(base)\n",
    "        left = [val for val in arr if val < base]\n",
    "        right = [val for val in arr if val >= base]\n",
    "        sort_left = self.sort(left)\n",
    "        sort_right = self.sort(right)\n",
    "        return sort_left+[base]+sort_right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        # 类比田忌赛马问题，让最快的相比，比不过，就换垫底的比\n",
    "\n",
    "        n = len(nums1)\n",
    "        sorted_nums1 = sorted(nums1) # 升序\n",
    "        # sorted_nums2 = sorted(nums2) # 降序\n",
    "\n",
    "        left, right = 0, n-1\n",
    "        res = [0] * n\n",
    "        for i in sorted(range(n), key=lambda x:-nums2[x]):\n",
    "            if sorted_nums1[right] > nums2[i]:\n",
    "                res[i] = sorted_nums1[right]\n",
    "                right -= 1\n",
    "            else:\n",
    "                res[i] = sorted_nums1[left]\n",
    "                left += 1\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        t = [(num, idx) for idx, num in enumerate(nums2)]\n",
    "        t.sort(reverse=True)\n",
    "        nums1.sort()\n",
    "        i = 0\n",
    "        j = len(t) - 1\n",
    "        ans = [0 for _ in range(j + 1)]\n",
    "        for n, idx in t:\n",
    "            if n >= nums1[j]:\n",
    "                ans[idx] = nums1[i]\n",
    "                i += 1\n",
    "            else:\n",
    "                ans[idx] = nums1[j]\n",
    "                j -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        # 田忌赛马问题\n",
    "        import heapq\n",
    "        hq = []\n",
    "        # 大顶堆\n",
    "        for i, num in enumerate(nums2):\n",
    "            heapq.heappush(hq, (num, i))\n",
    "        hq.sort()\n",
    "        nums1.sort()\n",
    "        \n",
    "        left = 0\n",
    "        right = len(nums1) - 1\n",
    "\n",
    "        for i in range(len(nums1) - 1, -1, -1):\n",
    "            val, idx = hq[i]\n",
    "            if nums1[right] > val:\n",
    "                nums2[idx] = nums1[right]\n",
    "                right -= 1\n",
    "            elif nums1[right] <= val:\n",
    "                nums2[idx] = nums1[left]\n",
    "                left += 1\n",
    "        \n",
    "        return nums2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        nums1.sort(reverse=True)\n",
    "        n = len(nums2)\n",
    "        s2 = sorted(zip(nums2, [i for i in range(n)]), reverse=True)\n",
    "        ans = [-1] * n\n",
    "        i, j = 0, n-1\n",
    "        for v, index in s2:\n",
    "            if nums1[i] > v:\n",
    "                ans[index] = nums1[i]\n",
    "                i+=1\n",
    "            else:\n",
    "                ans[index] = nums1[j]\n",
    "                j-=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        res = [0] * n\n",
    "        nums1.sort()\n",
    "        nums2 = [(num, i) for i, num in enumerate(nums2)]\n",
    "        nums2.sort()\n",
    "\n",
    "        l, r = 0, n-1\n",
    "\n",
    "        for i in range(n):\n",
    "            if nums1[i] > nums2[l][0]:\n",
    "                res[nums2[l][1]] = nums1[i]\n",
    "                l += 1\n",
    "            else:\n",
    "                res[nums2[r][1]] = nums1[i]\n",
    "                r -= 1\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def advantageCount(self,nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        nums3 = sorted(zip(nums2,range(len(nums2))))\n",
    "        nums1.sort()\n",
    "\n",
    "        # nums1[left] 是最小值，nums1[right] 是最大值\n",
    "        left, right = 0, n - 1\n",
    "        res = [0] * n\n",
    "\n",
    "        for i in range(len(nums1)-1,-1,-1):\n",
    "            val, index = nums3[i]\n",
    "            # val 是 nums2 中的最大值，index 是对应索引\n",
    "\n",
    "            if val < nums1[right]:\n",
    "                # 如果 nums1[right] 能胜过 val，那就自己上\n",
    "                res[index] = nums1[right]\n",
    "                right -= 1\n",
    "            else:\n",
    "                # 否则用最小值混一下，养精蓄锐\n",
    "                res[index] = nums1[left]\n",
    "                left += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        sorted_nums1 = sorted(nums1)\n",
    "        sorted_nums2 = sorted((num, i) for i, num in enumerate(nums2))\n",
    "        res = [0] * len(nums1)\n",
    "        remaining = []\n",
    "        \n",
    "        j = 0\n",
    "        for num in sorted_nums1:\n",
    "            if num > sorted_nums2[j][0]:\n",
    "                res[sorted_nums2[j][1]] = num\n",
    "                j += 1\n",
    "            else:\n",
    "                remaining.append(num)\n",
    "        \n",
    "        for num in remaining:\n",
    "            res[sorted_nums2[j][1]] = num\n",
    "            j += 1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\r\n",
    "        nums1.sort(reverse=True)\r\n",
    "        num2_idx = sorted([(n, i) for i, n in enumerate(nums2)], reverse=True)\r\n",
    "        ans = [0] * len(nums1)\r\n",
    "        idx = 0\r\n",
    "        tai = len(nums1) - 1\r\n",
    "        for n, i in num2_idx:\r\n",
    "            if nums1[idx] > n:\r\n",
    "                ans[i] = nums1[idx]\r\n",
    "                idx += 1\r\n",
    "            else:\r\n",
    "                ans[i] = nums1[tai]\r\n",
    "\r\n",
    "                tai -= 1\r\n",
    "\r\n",
    "        return ans\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        nums1.sort()\n",
    "        nums2_sorted = sorted(enumerate(nums2), key = lambda x: x[1])\n",
    "        # print(nums1)\n",
    "        # print(nums2_sorted)\n",
    "\n",
    "        res1 = []\n",
    "        res1_small = []\n",
    "        idx2 = 0\n",
    "        for n1 in nums1:\n",
    "            if n1 > nums2_sorted[idx2][1]:\n",
    "                res1.append(n1)\n",
    "                idx2 += 1\n",
    "            else:\n",
    "                res1_small.append(n1)\n",
    "\n",
    "        res1.extend(res1_small)\n",
    "        # print('res1: ', res1)\n",
    "\n",
    "        idx1 = 0\n",
    "        real_res = ['-inf' for _ in range(len(nums1))]\n",
    "        for idx, n2 in nums2_sorted:\n",
    "            real_res[idx] = res1[idx1]\n",
    "            idx1 += 1\n",
    "\n",
    "        return real_res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        ans = [-1] * n\n",
    "        nums1.sort()\n",
    "        a = sorted(zip(range(n), nums2), key=lambda p: p[1])\n",
    "        left, right = 0, n-1\n",
    "        for x in nums1:\n",
    "            if x > a[left][1]:\n",
    "                ans[a[left][0]] = x\n",
    "                left += 1\n",
    "            else:\n",
    "                ans[a[right][0]] = x\n",
    "                right -= 1\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "田忌赛马\n",
    "如何用代码表示呢？\n",
    "如果不关注顺序的话，可以直接排序，然后错位对齐\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        f = [[0 for _ in range(2)] for _ in range(n)]\n",
    "        wait = []\n",
    "        ans  = [-1] * n\n",
    "        for i,x in enumerate(nums2):\n",
    "            f[i] = [x, i]\n",
    "        nums1.sort()\n",
    "        f.sort()\n",
    "        i, j = 0, 0\n",
    "        while i<n:\n",
    "            if nums1[i] > f[j][0]:\n",
    "                ans[f[j][1]] = nums1[i]\n",
    "                j+=1\n",
    "            else:\n",
    "                wait.append(nums1[i])\n",
    "            i+=1\n",
    "            # print('wait : ', wait)\n",
    "            # print('ans : ', ans)\n",
    "\n",
    "        # print(nums1)\n",
    "        # print(f)\n",
    "  \n",
    "        for k in range(n):\n",
    "            if len(wait) == 0:\n",
    "                break\n",
    "            if ans[k] == -1:\n",
    "                ans[k] = wait.pop()\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\r\n",
    "        n = len(nums1)\r\n",
    "        # 给 nums2 降序排序\r\n",
    "        maxpq = [(val, i) for i, val in enumerate(nums2)]\r\n",
    "        sorted_maxpq = sorted(maxpq, key=lambda x: x[0])\r\n",
    "        # 给 nums1 升序排序\r\n",
    "        nums1.sort()\r\n",
    "        # nums1[left] 是最小值，nums1[right] 是最大值\r\n",
    "        left, right = 0, n - 1\r\n",
    "        res = [0] * n\r\n",
    "        k = n\r\n",
    "        while k > 0:\r\n",
    "            [val,i] = sorted_maxpq.pop()\r\n",
    "            if nums1[right] > val:\r\n",
    "                res[i] = nums1[right]\r\n",
    "                right -= 1\r\n",
    "            else:\r\n",
    "                res[i] = nums1[left]\r\n",
    "                left += 1\r\n",
    "            k -= 1\r\n",
    "        return res\r\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        nums1.sort()\n",
    "        tmp = sorted([[nums2[i], i] for i in range(len(nums2))])\n",
    "        res = [0] * len(nums1)\n",
    "        l = 0\n",
    "        r = len(nums1) - 1\n",
    "        k = len(nums2) - 1\n",
    "        while l <= r:\n",
    "            n, idx = tmp[k]\n",
    "            if nums1[r] > n:\n",
    "                res[idx] = nums1[r]\n",
    "                r -= 1\n",
    "            else:\n",
    "                res[idx] = nums1[l]\n",
    "                l += 1\n",
    "            k -= 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        n = len(nums2)\n",
    "        temp = sorted(zip(nums2, range(n)))\n",
    "        index = [t[1] for t in temp]\n",
    "        nums2 = [t[0] for t in temp]\n",
    "        nums1 = sorted(nums1)\n",
    "        ans = nums1.copy()\n",
    "        left = 0\n",
    "        right = n - 1\n",
    "        for i in range(n):\n",
    "            if nums2[left] < nums1[i]:\n",
    "                ans[index[left]] = nums1[i]\n",
    "                left += 1\n",
    "            else:\n",
    "                ans[index[right]] = nums1[i]\n",
    "                right -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        nums1 = sorted(nums1,reverse=True)\n",
    "        nums2 = [(i,nums2[i]) for i in range(len(nums2))]\n",
    "        nums2 = sorted(nums2,key=lambda x:x[1],reverse=True)\n",
    "        num =[0 for i in range(len(nums1))]\n",
    "        start = 0\n",
    "        end = len(nums1)-1\n",
    "        for i in range(len(nums2)):\n",
    "            x = nums2[i]\n",
    "            if x[1]<nums1[start]:\n",
    "                num[x[0]]=nums1[start]\n",
    "                start+=1\n",
    "            else:\n",
    "                num[x[0]]=nums1[end]\n",
    "                end-=1\n",
    "            \n",
    "        return num\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        ans = [None]*len(nums1)\n",
    "        rank = []\n",
    "        for i, n in enumerate(nums2):\n",
    "            rank.append([i, n])\n",
    "        rank.sort(key=lambda x:x[1])\n",
    "        nums1.sort(reverse=True)\n",
    "\n",
    "        l = 0\n",
    "        r = len(rank)-1\n",
    "        while nums1:\n",
    "            a = nums1.pop()\n",
    "            if a > rank[l][1]:\n",
    "                ans[rank[l][0]] = a\n",
    "                l += 1\n",
    "            else:\n",
    "                ans[rank[r][0]] = a\n",
    "                r -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://labuladong.gitee.io/algo/di-yi-zhan-da78c/shou-ba-sh-48c1d/tian-ji-sa-7baa4/\n",
    "# 田忌赛马，最优策略，双指针,最大堆\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        # 给 nums1 升序排序\n",
    "        nums1.sort()\n",
    "\n",
    "        # 给 nums2 降序排序\n",
    "        pq = []\n",
    "        for i, val in enumerate(nums2):\n",
    "            # heapq是最小堆。这里的-val是负数，意思就是搞成最大堆\n",
    "            heapq.heappush(pq, (-val, i))\n",
    "        \n",
    "        # nums1[left] 是最小值，nums1[right] 是最大值\n",
    "        left, right = 0, len(nums1) - 1\n",
    "        res = [0] * len(nums1)\n",
    "        while pq:\n",
    "            # maxval 是 nums2 中的最大值，idx 是对应索引\n",
    "            val, idx = heapq.heappop(pq)\n",
    "            max_val = -val\n",
    "            if max_val < nums1[right]:\n",
    "                # 如果 nums1[right] 能胜过 maxval，那就自己上\n",
    "                res[idx] = nums1[right]\n",
    "                right -= 1\n",
    "            else:\n",
    "                # 否则用最小值混一下，养精蓄锐\n",
    "                res[idx] = nums1[left]\n",
    "                left += 1\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:  \n",
    "        length = len(nums1)\n",
    "        nums1.sort()\n",
    "\n",
    "        # enumerate : index, val\n",
    "        max_heap = [(-val, i) for i, val in enumerate(nums2)]\n",
    "        heapq.heapify(max_heap)\n",
    "\n",
    "        # double pointer \n",
    "        left, right = 0, length - 1 \n",
    "        res = [0] * length\n",
    "        while max_heap:\n",
    "            val, index = heapq.heappop(max_heap)\n",
    "            val_num2 = - val\n",
    "            if val_num2 < nums1[right]:\n",
    "                res[index] = nums1[right]\n",
    "                right -= 1\n",
    "            else:\n",
    "                res[index] = nums1[left]\n",
    "                left += 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        n = len(nums2)\n",
    "        nums1.sort()\n",
    "        nums2 = [(-val, i) for i, val in enumerate(nums2)]\n",
    "        heapq.heapify(nums2)\n",
    "        left = 0\n",
    "        right = n - 1\n",
    "        res = [0] * n\n",
    "        while nums2:\n",
    "            val, i = heapq.heappop(nums2)\n",
    "            val = -val\n",
    "            if nums1[right] > val:\n",
    "                res[i] = nums1[right]\n",
    "                right -= 1\n",
    "            else:\n",
    "                res[i] = nums1[left]\n",
    "                left += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        nums1 = sorted(nums1)\n",
    "        nums2 = [[num, idx] for (num, idx) in zip(nums2, range(n))]\n",
    "        nums2 = sorted(nums2, key=lambda x: x[0])\n",
    "        result = [0] * len(nums2)\n",
    "        L, R = 0, n - 1\n",
    "        for x in nums1:\n",
    "            if x > nums2[L][0]:  ## x 是否可以匹配当前最小值\n",
    "                min_value_idx = nums2[L][1]  ## 获取当前最小值的 index\n",
    "                result[min_value_idx] = x\n",
    "                L += 1\n",
    "            else:   ## x 无法成功匹配, 因此将其分配给最大值\n",
    "                max_value_idx = nums2[R][1]  ## 获取当前最大值的 idx\n",
    "                result[max_value_idx] = x \n",
    "                R -= 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        nums1 = sorted(nums1)\n",
    "        nums2 = [(-x, i) for i, x in enumerate(nums2)]\n",
    "        heapq.heapify(nums2)\n",
    "        # print(nums2)\n",
    "        res = [0] * len(nums1)\n",
    "        s = 0\n",
    "        e = len(nums1)-1\n",
    "        while s <= e:\n",
    "            max_v, j = heapq.heappop(nums2)\n",
    "            max_v = -max_v\n",
    "            if max_v < nums1[e]:\n",
    "                res[j] = nums1[e]\n",
    "                e -= 1\n",
    "            else:\n",
    "                res[j] = nums1[s]\n",
    "                s += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        nums1.sort(reverse=True)\n",
    "        nums2_bak = nums2.copy()\n",
    "        nums2.sort(reverse=True)\n",
    "        left, right = 0, len(nums1) - 1\n",
    "        match_pair = {}\n",
    "        for ele in nums2:\n",
    "            if ele < nums1[left]:\n",
    "                # print(f'ele: {ele}, pair: {nums1[left]}')\n",
    "                if ele in match_pair:\n",
    "                    match_pair[ele].append(nums1[left])\n",
    "                else:\n",
    "                    match_pair[ele] = [nums1[left]]\n",
    "                left += 1\n",
    "            else:\n",
    "                # print(f'ele: {ele}, pair: {nums1[right]}')\n",
    "                if ele in match_pair:\n",
    "                    match_pair[ele].append(nums1[right])\n",
    "                else:\n",
    "                    match_pair[ele] = [nums1[right]]\n",
    "                right -= 1\n",
    "        ret = []\n",
    "        for ele in nums2_bak:\n",
    "            ret.append(match_pair[ele].pop())\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        #max_heap = [(-num, i) for i, num in enumerate(nums2)]\n",
    "        #heapq.heapify(max_heap)\n",
    "        max_heap=[]\n",
    "        for i,num in enumerate(nums2):\n",
    "            heapq.heappush(max_heap,[-num,i])\n",
    "        nums1.sort()\n",
    "        res = [0] * n\n",
    "        left, right = 0, n - 1\n",
    "        \n",
    "        while max_heap:\n",
    "            max_p, i = heapq.heappop(max_heap)\n",
    "            max_p = -max_p\n",
    "            \n",
    "            if max_p < nums1[right]:\n",
    "                res[i] = nums1[right]\n",
    "                right -= 1\n",
    "            else:\n",
    "                res[i] = nums1[left]\n",
    "                left += 1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        nums = [[-ele, i] for i, ele in enumerate(nums2)]\n",
    "        heapq.heapify(nums)\n",
    "        nums1.sort()\n",
    "        left, right = 0, len(nums1) - 1\n",
    "        res = [0] * len(nums2)\n",
    "        while nums:\n",
    "            cur, ind = heapq.heappop(nums)\n",
    "            val = -cur\n",
    "            if nums1[right] > val:\n",
    "                res[ind] = nums1[right]\n",
    "                right -= 1\n",
    "            else:\n",
    "                res[ind] = nums1[left]\n",
    "                left += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "\n",
    "        # 预处理nums2\n",
    "        tm = []\n",
    "        for i, x in enumerate(nums2):\n",
    "            tm.append([x, i])\n",
    "        tm.sort(key=lambda y: -y[0])\n",
    "        # print(tm)\n",
    "        nums1.sort()\n",
    "        n = len(nums1)\n",
    "        left = 0\n",
    "        right = n - 1\n",
    "        res = [0] * n \n",
    "        for i in range(n):\n",
    "            if nums1[right] > tm[i][0]:\n",
    "                res[tm[i][1]] = nums1[right]\n",
    "                right -= 1\n",
    "            else:\n",
    "                res[tm[i][1]] = nums1[left]\n",
    "                left += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        # les = len(nums1)\n",
    "        # lst = [_ for _ in range(les)]\n",
    "        # zipped = list(zip(lst, nums2))\n",
    "        # zipped.sort(key = lambda x: x[1])\n",
    "        # lst = [_[0] for _ in zipped]\n",
    "        # lst2 = [_[1] for _ in zipped]\n",
    "        # res = [[0] for _ in range(les)]\n",
    "        # nums1.sort()\n",
    "        # s = 0\n",
    "        # e = les-1\n",
    "        # for i in range(les):\n",
    "        #     if nums1[i] > lst2[s]:\n",
    "        #         res[lst[s]] =  nums1[i]\n",
    "        #         s += 1\n",
    "        #     else:\n",
    "        #         res[lst[e]] = nums1[i]\n",
    "        #         e -= 1\n",
    "        # return res\n",
    "\n",
    "        n = len(nums1)\n",
    "        n1 = nums1[:]\n",
    "        n2 = nums2[:]\n",
    "        n1.sort()\n",
    "        n2.sort()\n",
    "\n",
    "        useless = []\n",
    "        dic = dict()\n",
    "        count = 0\n",
    "        for i in range(n):\n",
    "            if n1[i] > n2[count]:\n",
    "                dic[n2[count]] = dic.get(n2[count], []) + [n1[i]]\n",
    "                count += 1\n",
    "            else:\n",
    "                useless.append(n1[i])\n",
    "        res = []\n",
    "        count = 0\n",
    "        for i in nums2:\n",
    "            if i in dic.keys():\n",
    "                if len(dic[i]) > 0:\n",
    "                    res.append(dic[i][0])\n",
    "                    dic[i] = dic[i][1:]\n",
    "                else:\n",
    "                    res.append(useless[count])\n",
    "                    count+=1\n",
    "            else:\n",
    "                res.append(useless[count])\n",
    "                count+=1\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 田忌赛马的解题思路：【用双指针，从最快的马开始，比得过就比，比不过就送】\n",
    "# 将齐王和田忌的马按照战斗力排序，然后按照排名一一对比。\n",
    "# 如果田忌的马能赢，那就比赛，如果赢不了，那就换个垫底的来送人头，保存实力。\n",
    "# 更进一步的，根据这个思路，我们需要对两个数组排序，但是 nums2 中元素的顺序不能改变\n",
    "# 因为计算结果的顺序依赖 nums2 的顺序，所以不能直接对 nums2 进行排序，而是利用其他数据结构来辅助。\n",
    "# 可以使用SortedList或者heapq来解题\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        nums2_q = []\n",
    "        for i, num in enumerate(nums2):\n",
    "            nums2_q.append((-num, i))\n",
    "        # nums2_q = heapq.heapify(nums2_tmp)\n",
    "        heapq.heapify(nums2_q)\n",
    "        nums1.sort()\n",
    "        print( nums2_q)\n",
    "        res = [0] * n\n",
    "        left = 0\n",
    "        right = n - 1\n",
    "        # print(nums2_q)\n",
    "        for i in range(n-1, -1, -1):\n",
    "            curr = heapq.heappop(nums2_q)\n",
    "            if nums1[right] > -curr[0]:\n",
    "                res[curr[1]] = nums1[right]\n",
    "                right -= 1\n",
    "            else:\n",
    "                res[curr[1]] = nums1[left]\n",
    "                left += 1\n",
    "        return res\n",
    "\n",
    "\n",
    "        # n = len(nums1)\n",
    "        # sorted_nums2 = SortedList(key = lambda x: x[1])\n",
    "        # for i, num in enumerate(nums2):\n",
    "        #     sorted_nums2.add((i, num))\n",
    "        # nums1.sort()\n",
    "        # res = [None] * n\n",
    "        # left = 0\n",
    "        # right = n - 1\n",
    "        # # while left <= right:\n",
    "        # for i in range(n - 1, -1, -1):\n",
    "        #     if nums1[right] > sorted_nums2[i][1]:\n",
    "        #         res[sorted_nums2[i][0]] = nums1[right]\n",
    "        #         right -= 1\n",
    "        #     else:\n",
    "        #         res[sorted_nums2[i][0]] = nums1[left]\n",
    "        #         left += 1\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "\n",
    "        p = []\n",
    "        for i in range(nums2.__len__()):\n",
    "            nums2[i] = [nums2[i]]\n",
    "            p.append(nums2[i])\n",
    "\n",
    "        nums1 = sorted(nums1)\n",
    "\n",
    "        nums2 = sorted(nums2, key=lambda x: x[0])\n",
    "        i = 0\n",
    "        j = 0\n",
    "\n",
    "        not_used = []\n",
    "        while i < nums1.__len__() and j < nums2.__len__():\n",
    "            if nums1[i] <= nums2[j][0]:\n",
    "                not_used.append(i)\n",
    "                i += 1\n",
    "            else:\n",
    "                nums2[j].append(nums1[i])\n",
    "                i += 1\n",
    "                j += 1\n",
    "\n",
    "        while j < nums2.__len__():\n",
    "            nums2[j].append(nums1[not_used.pop()])\n",
    "            j += 1\n",
    "\n",
    "        ans = []\n",
    "        for item in p:\n",
    "            ans.append(item[1])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        Maxheapq = [(-val,i) for i,val in enumerate(nums2)]\n",
    "        heapq.heapify(Maxheapq) #将nums2的数组倒序\n",
    "        nums1.sort()\n",
    "        n = len(nums1)\n",
    "        res = [0] * n\n",
    "        #定义双指针\n",
    "        left = 0\n",
    "        right = len(nums1) - 1\n",
    "        print(Maxheapq)\n",
    "        while(Maxheapq):\n",
    "            maxVal,i = heapq.heappop(Maxheapq)\n",
    "            maxVal = -maxVal\n",
    "            if(maxVal >= nums1[right]):\n",
    "                res[i] = nums1[left]\n",
    "                left += 1\n",
    "            else:\n",
    "                res[i] = nums1[right]\n",
    "                right -= 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "\n",
    "        nums1_idt=sorted(range(len(nums1)),key=lambda x:nums1[x])\n",
    "        nums2_idt=sorted(range(len(nums2)),key=lambda x:nums2[x])\n",
    "\n",
    "        idt_1=len(nums1_idt)-1\n",
    "        idt_2=len(nums2_idt)-1\n",
    "\n",
    "        result=[None for i in range(len(nums2_idt))]\n",
    "        result_set=set(range(len(nums2_idt)))\n",
    "\n",
    "        while idt_2>=0:\n",
    "            if nums1[nums1_idt[idt_1]]>nums2[nums2_idt[idt_2]]:\n",
    "                result[nums2_idt[idt_2]]=nums1[nums1_idt[idt_1]]\n",
    "                result_set.remove(nums1_idt[idt_1])\n",
    "                idt_1-=1\n",
    "                idt_2-=1\n",
    "\n",
    "            else:\n",
    "                idt_2-=1\n",
    "        print(result)\n",
    "        if result_set:\n",
    "            for idt in range(len(result)):\n",
    "                if result[idt]==None:\n",
    "                    result[idt]=nums1[result_set.pop()]\n",
    "\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        dic2 = {}\n",
    "        for k,v in enumerate(nums2):\n",
    "            dic2[k] = v\n",
    "        res = [0]*len(nums2)\n",
    "        nums1_new = sorted(nums1,reverse=True)\n",
    "        nums2_new = sorted(dic2.items(),key=lambda x: x[1],reverse=True)\n",
    "        left,right = 0,len(nums2) - 1\n",
    "        for i in range(len(nums2)):\n",
    "            if nums1_new[left] > nums2_new[i][1]:\n",
    "                res[nums2_new[i][0]] = nums1_new[left]\n",
    "                left += 1\n",
    "            else:\n",
    "                res[nums2_new[i][0]] = nums1_new[right]\n",
    "                right -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        nums2_copy = sorted(nums2)\n",
    "        nums1.sort()\n",
    "\n",
    "        hashmap = {key: [] for key in nums2}\n",
    "        q = collections.deque()\n",
    "\n",
    "        j = 0\n",
    "        for val in nums1:\n",
    "            if val > nums2_copy[j]:\n",
    "                hashmap.get(nums2_copy[j]).append(val)\n",
    "                j += 1\n",
    "            else:\n",
    "                q.append(val)\n",
    "\n",
    "        res = [0] * len(nums2)\n",
    "        for i in range(len(nums2)):\n",
    "            if len(hashmap.get(nums2[i])) > 0:\n",
    "                res[i] = hashmap.get(nums2[i]).pop()\n",
    "            else:\n",
    "                res[i] = q.pop()\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        nums1.sort()\n",
    "        nums3 ,n = nums2[:], len(nums1)\n",
    "        nums3.sort()\n",
    "        map_dict = defaultdict(list)\n",
    "        i, j, k = 0, n-1, n-1 \n",
    "        while k>=0:\n",
    "            if nums1[j] > nums3[k]:\n",
    "                map_dict[nums3[k]].append(nums1[j])\n",
    "                k -= 1\n",
    "                j -= 1\n",
    "            else:\n",
    "                map_dict[nums3[k]].append(nums1[i]) \n",
    "                k -= 1\n",
    "                i += 1\n",
    "        #print(map_dict)\n",
    "        res = []\n",
    "        for num in nums2:\n",
    "            res.append(map_dict[num].pop())\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        l = len(nums1)\n",
    "\n",
    "        sort1 = np.argsort(nums1)\n",
    "        sort2 = np.argsort(nums2)\n",
    "\n",
    "        result = [0]*l\n",
    "\n",
    "        i, j = 0, 0\n",
    "        unused1 = []\n",
    "        while j < l and i < l:\n",
    "            n1 = nums1[sort1[i]]\n",
    "            n2 = nums2[sort2[j]]\n",
    "\n",
    "            if n1>n2:\n",
    "                result[sort2[j]] = n1\n",
    "                j += 1\n",
    "                i += 1\n",
    "            else:\n",
    "                i += 1\n",
    "                unused1.append(n1)\n",
    "    \n",
    "        while j < l:\n",
    "            result[sort2[j]] = unused1[0]\n",
    "            unused1.pop(0)\n",
    "            j += 1\n",
    "\n",
    "        # print(sort2)\n",
    "        # print(result)\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        d = {}\n",
    "        rank = []\n",
    "        for i, n in enumerate(nums2):\n",
    "            rank.append([i, n])\n",
    "        rank.sort(key=lambda x:x[1])\n",
    "        nums1.sort(reverse=True)\n",
    "        l = 0\n",
    "        r = len(rank)-1\n",
    "        while nums1:\n",
    "            a = nums1.pop()\n",
    "            if a > rank[l][1]:\n",
    "                d[rank[l][0]] = a\n",
    "                l += 1\n",
    "            else:\n",
    "                d[rank[r][0]] = a\n",
    "                r -= 1\n",
    "        return [d[i] for i in range(len(rank))]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        s1, s2 = sorted(nums1), sorted(nums2)\n",
    "        d = collections.defaultdict(list)\n",
    "\n",
    "        delta = 0\n",
    "        tmp = []\n",
    "        for i in range(len(s2)):\n",
    "            while (i + delta) < len(s2):\n",
    "                if s1[i + delta] <= s2[i]:\n",
    "                    tmp.append(s1[i + delta])\n",
    "                    delta += 1\n",
    "                else:\n",
    "                    d[s2[i]].append(s1[i + delta])\n",
    "                    break\n",
    "\n",
    "        res = []\n",
    "\n",
    "        for n in nums2:\n",
    "            if n in d and d[n]:\n",
    "                res.append(d[n].pop())\n",
    "            else:\n",
    "                res.append(tmp.pop())\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def advantageCount(self, A: List[int], B: List[int]) -> List[int]:\r\n",
    "        nums1 = [(A[i], i) for i in range(len(A))]\r\n",
    "        nums2 = [(B[i], i) for i in range(len(B))]\r\n",
    "        nums1 = sorted(nums1, reverse=True)\r\n",
    "        nums2 = sorted(nums2, reverse=True)        \r\n",
    "        stack = nums1[:]\r\n",
    "        p1 = 0\r\n",
    "        p2 = len(nums1) - 1\r\n",
    "        res = []\r\n",
    "        for x, idx2 in nums2:\r\n",
    "            if stack[p1][0] > x:\r\n",
    "                res.append(stack[p1][1])\r\n",
    "                p1 += 1\r\n",
    "            else:\r\n",
    "                res.append(stack[p2][1])\r\n",
    "                p2 -= 1\r\n",
    "        \r\n",
    "        # print(res)\r\n",
    "\r\n",
    "        res_val = [None] * len(nums1)\r\n",
    "\r\n",
    "        for i in range(len(nums1)):\r\n",
    "            idx2 = nums2[i][1]\r\n",
    "            res_val[idx2] = A[res[i]]\r\n",
    "        \r\n",
    "        return res_val\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        n1 = sorted(nums1)\n",
    "        n2 = sorted(enumerate(nums2), key=lambda x:x[1])\n",
    "        n2i = {x[0]:i for i,x in enumerate(n2)}\n",
    "        i = 0\n",
    "        j = 0\n",
    "        que1 = deque()\n",
    "        que2 = deque()\n",
    "        while(j<n):\n",
    "            while (i<n and n1[i]<=n2[j][1]):\n",
    "                que1.append(n1[i])\n",
    "                i+=1\n",
    "            if i<n:\n",
    "                que2.append(n1[i])\n",
    "                i+=1\n",
    "                j+=1\n",
    "            else:\n",
    "                break\n",
    "        tmp = que2+que1\n",
    "        r = [0]*n\n",
    "        for i in range(n):\n",
    "            r[i] = tmp[n2i[i]]\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        # race use the slow horse to compare with the fasters horse\n",
    "        # consider about the most bad situation if the slowest horse in nums2 is bigger or equare than the fastest horse in nums1, no matter how arrange the nums1, the advange is 0,so just return\n",
    "        # otherwise we first use the fastest in nums1 to compare the one in nums2, which it is the fastest can be beat by the fastest in nums1,\n",
    "        n = len(nums1)\n",
    "        ans = []\n",
    "        nums1 = sorted(nums1, key=lambda x: -x)\n",
    "        p = sorted([(num, i) for i, num in enumerate(nums2)], key=lambda x: -x[0])\n",
    "        i = 0 #指向nums1\n",
    "        j = 0 #指向p，也就是nums2\n",
    "        mp = {} #记录nums1比nums2大的几个数，nums2的下标->nums1中比这个下标大的数\n",
    "        while i < n:\n",
    "            while j < n and p[j][0] >= nums1[i]:\n",
    "                j += 1\n",
    "            if j == n:\n",
    "                break\n",
    "            mp[p[j][1]] = nums1[i]\n",
    "            i += 1\n",
    "            j += 1\n",
    "        # 这个时候i指向nums1中第一个无法比nums2中的任意数都大的位置，有可能是n，也就是没有这个数，nums1中的数可以找到都比nums2中的数大\n",
    "        for k, num in enumerate(nums2):\n",
    "            if k in mp:\n",
    "                ans.append(mp[k])\n",
    "            else:\n",
    "                ans.append(nums1[i])\n",
    "                i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        max_heap = []\n",
    "        for idx in range(len(nums2)):\n",
    "            heapq.heappush(max_heap, self.State(idx, nums2[idx]))\n",
    "\n",
    "        nums1.sort()\n",
    "\n",
    "        res = [None]*len(nums1)\n",
    "        l, r = 0, len(nums1)-1\n",
    "        \n",
    "        while l <= r:\n",
    "            cur_state = heapq.heappop(max_heap)\n",
    "            idx = cur_state.idx\n",
    "            val = cur_state.val\n",
    "            if nums1[r] > val:\n",
    "                res[idx] = nums1[r]\n",
    "                r -= 1\n",
    "            else:\n",
    "                res[idx] = nums1[l]\n",
    "                l += 1\n",
    "\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "    class State:\n",
    "        def __init__(self, idx, val):\n",
    "            self.idx = idx\n",
    "            self.val = val\n",
    "        \n",
    "        def __lt__(self, other):\n",
    "            if self.val > other.val:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        idx_mapping = collections.defaultdict(list)\n",
    "        for i, v in enumerate(nums2):\n",
    "            idx_mapping[v].append(i)\n",
    "        \n",
    "        nums2.sort(reverse = True)\n",
    "        nums1.sort()\n",
    "        l, r = 0, len(nums1)-1\n",
    "        res = [-1 for _ in nums1]\n",
    "        for i in range(len(nums2)):\n",
    "            n2 = nums2[i]\n",
    "            if nums1[r] > n2:\n",
    "                res[idx_mapping[n2].pop()] = nums1[r]\n",
    "                r -= 1\n",
    "            else:\n",
    "                res[idx_mapping[n2].pop()] = nums1[l]\n",
    "                l += 1\n",
    "           \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        max_heap = []\n",
    "        for idx in range(len(nums2)):\n",
    "            heapq.heappush(max_heap, self.State(idx, nums2[idx]))\n",
    "\n",
    "        nums1.sort()\n",
    "\n",
    "        res = [None]*len(nums1)\n",
    "        l, r = 0, len(nums1)-1\n",
    "        \n",
    "        while l <= r:\n",
    "            cur_state = heapq.heappop(max_heap)\n",
    "            idx = cur_state.idx\n",
    "            val = cur_state.val\n",
    "            if nums1[r] > val:\n",
    "                res[idx] = nums1[r]\n",
    "                r -= 1\n",
    "            else:\n",
    "                res[idx] = nums1[l]\n",
    "                l += 1\n",
    "\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "    class State:\n",
    "        def __init__(self, idx, val):\n",
    "            self.idx = idx\n",
    "            self.val = val\n",
    "        \n",
    "        def __lt__(self, other):\n",
    "            if self.val > other.val:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
